package tree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class PreOrderTraverse_94_1 {

    public static void main(String[] args) {

    }

    public List<Integer> preorderTraversal(TreeNode_94 root) {
        //返回的结果集
        List<Integer> res = new ArrayList<>();
        //如果根节点为空，那么就直接返回空的结果集，没遍历的必要了
        if (root == null) return res;
        //创建一个栈
        Deque<TreeNode_94> stack = new LinkedList<>();
        //将当前的根节点放入栈中
        stack.push(root);
        //如果当前的栈不为空，那就一直循环
        while (!stack.isEmpty()) {
            //从栈中取出一个结点
            root = stack.pop();
            //由于是前序遍历，所以将当前的结点直接存入结果集合中
            res.add(root.val);
            //此处的顺序比较有将就，前序是：根 → 左 → 右
            //所以我们要先将右结点压入栈，再将左结点压入栈
            //因为左结点是最晚压入栈的，所以取的时候，会先取左结点，然后是右结点，就符合前序遍历了
            if (root.right != null) stack.push(root.right);//如果当前结点的右子结点不为空，就把右子结点压入栈
            if (root.left != null) stack.push(root.left);//如果当前节点的左子结点不为空，就把左子结点压入栈
        }
        return res;
    }
}
